﻿/*
题目：最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

https://leetcode.cn/problems/longest-valid-parentheses/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // 将所有破坏匹配规则的 下标置为 False
    int longestValidParentheses(string s) {
        stack<int> stk;
        vector<bool> marks(s.size(), true);

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            }
            else if (s[i] == ')') {
                if (!stk.empty() && s[stk.top()] == '(') {
                    stk.pop();
                    continue;
                }

                // 否则，破坏当前匹配规则
                stk.push(i);
                while (!stk.empty()) {
                    auto top = stk.top();
                    marks[top] = false;     // 当前括号破坏了匹配
                    stk.pop();
                }
            }
        }

        while (!stk.empty()) {
            auto top = stk.top();
            marks[top] = false;     // 当前括号破坏了匹配
            stk.pop();
        }

        int cur = 0, res = 0;
        for (int i = 0; i < marks.size(); i++) {
            if (marks[i] == true) {
                cur++;
                res = max(res, cur);
            }
            else {
                cur = 0;
            }
        }

        return res;
    }
};
